//给你一个二叉树的根节点 root ， 检查它是否轴对称。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,2,2,3,4,4,3]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,2,null,3,null,3]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [1, 1000] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 进阶：你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1842 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

class SymmetricTree {
    public static void main(String[] args) {
        Solution solution = new SymmetricTree().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
//        public boolean isSymmetric(TreeNode root) {
//            if (root == null) {
//                return true;
//            }
//            return compare(root.left, root.right);
//        }

        /**
         * 判断左右节点是否对称
         *
         * @param left
         * @param right
         * @return true表示对称，false表示不对称
         */
//        boolean compare(TreeNode left, TreeNode right) {
//            if (left == null && right == null) return true; // 左右节点都为空，则是对称的
//            else if (left == null && right != null) return false;  // 左节点为空，右节点不为空，此时不对称
//            else if (left != null && right == null) return false;  // 左节点不为空，右节点为空，此时不对称
//            else if (left.val != right.val) return false;   // 左右节点的值不相等，此时不对称
//            else {  // 剩下的是左右节点相等的情况,此时递归判断孩子节点
//                boolean outside = compare(left.left, right.right); // 判断外侧
//                boolean inside = compare(left.right, right.left);  // 判断内侧
//                return inside && outside; // 如果该节点的左右孩子节点都是对称的，返回true
//            }
//        }
//    }

        /**
         * 使用队列实现
         *
         * @param root
         * @return
         */
    /*public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列进行比较
        if (root == null) {
            return true;
        }

        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            // 成对的取出元素进行判断
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();

            if (leftNode == null && rightNode == null) continue;    // 左右节点为空，为对称

            if (leftNode == null && rightNode != null
                    || leftNode != null && rightNode == null
                    || leftNode.val != rightNode.val)
                return false;   // 三种情况为不对成

            queue.offer(leftNode.left);     // 加入左节点左孩子
            queue.offer(rightNode.right);   // 加入右节点右孩子
            queue.offer(leftNode.right);    // 加入左节点右孩子
            queue.offer(rightNode.left);    // 加入右节点左孩子
        }

        return true;
    }*/
    /* public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return compare(root.left, root.right);
    }*/

        /**
         * 判断左右节点是否对称
         *
         * @param left
         * @param right
         * @return true表示对称，false表示不对称
         */
    /*boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        else if (left != null && right == null) return false;
        else if (left == null && right != null) return false;
        else if (left.val != right.val) return false;
        else {
            boolean inside = compare(left.right, right.left);
            boolean outside = compare(left.left, right.right);
            return inside & outside;
        }
    }*/


    /*boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        else if ((left == null && right != null) || left != null && right == null) return false;
        else if (left.val != right.val) return false;
        else {
            return compare(left.right, right.left) & compare(left.left, right.right);
        }
    }*/


        // 使用队列或者栈
        public boolean isSymmetric(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root.left);
            queue.offer(root.right);
            while (!queue.isEmpty()) {
                TreeNode node1 = queue.poll();
                TreeNode node2 = queue.poll();

                if (node1 == null && node2 == null) continue;

                if ((node1 != null && node2 == null) && (node1 == null && node2 != null)) return false;

                queue.offer(node1.right);
                queue.offer(node2.left);
                queue.offer(node1.left);
                queue.offer(node2.right);
            }
            return true;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}
